\documentclass[compact]{article}
\usepackage{parskip}
\usepackage{xcolor}
\usepackage[english]{babel}
\usepackage{cite}
\usepackage{url}
\usepackage{booktabs}
\usepackage{mdwlist}
\usepackage{textcomp}
\usepackage{fullpage}
\usepackage[left=2cm,top=1cm,right=2cm,nohead,nofoot]{geometry}
\usepackage{ulem}
\usepackage{hyperref}
\usepackage{fancyhdr}
\usepackage{listings}

\definecolor{bluekeywords}{rgb}{0.13,0.13,1}
\definecolor{greencomments}{rgb}{0,0.5,0}
\definecolor{redstrings}{rgb}{0.9,0,0}

\lstset{language=C,  
showspaces=false,
showtabs=false,
breaklines=true,
showstringspaces=false,
breakatwhitespace=true,
escapeinside={(*@}{@*)},
commentstyle=\color{greencomments},
keywordstyle=\color{bluekeywords}\bfseries,
stringstyle=\color{redstrings},
basicstyle=\ttfamily
}


\fancyhead[LO,LE]{Report of assignment 2}
\fancyhead[RO,RE]{\textit{System Programming in C}}
\fancyfoot[CO,CE]{Delft University of Technology, Department of EEMCS}
\fancyfoot[RO, LE] {\thepage} %add \thepage for page number
\renewcommand{\headrulewidth}{0.1pt}
\renewcommand{\footrulewidth}{0.1pt}
\voffset = -25pt
\headheight = 45pt
\headsep = 8pt
\topmargin = 10pt
\textheight = 660pt
\setlength{\parindent}{0pt}
\setlength{\parskip}{0pt}
\setlength{\parsep}{0pt}
\setlength{\topskip}{0pt}
\linespread{1}

\title{\textbf{Programming in C}\\ Assignment 2}
\date{October 2012}
\author{Jacco van der Spek - 4002512\\Mario Voorsluys - 4048482\\ \\Delft University of Technology\\Department of EEMCS}



\begin{document}
\maketitle
\pagestyle{fancy}
\newpage

\section{Introduction}
The program that has been designed is used to read a circuit description from a file in such a way that it can be used for circuit simulation. The circuit description is given in a  `Verilog netlist' format. This is a text file which describes the circuit in terms of wires, gates and the way they are connected. To verify the correctness of the reading process, the read netlist has to be re-generated and compared to the original netlist.

In this document the functions that are created will be explained. Some functions will be explained in more detail than others. This is due to the fact that some functions can be easily understood from the code.
 
\section{Netlist}
\begin{lstlisting}
void to_lower_case(char *line)
\end{lstlisting}
This function converts the given line to lower case characters the c-function $tolower()$ is used for this task. 

\begin{lstlisting}
void read_line(FILE *fp, char line[])
\end{lstlisting}
This functions reads a line from a file with the use of $fgets$ if there are no more lines to read an empty line is returned.

\begin{lstlisting}
int isInput(char *line)
\end{lstlisting}
This function first converts the input line into lower case then it does a $strstr$ operation on the input line. The $strstr$ operation looks in the given line for ``input". The result of the $strstr$ operation, a pointer to where the result is, is stored. Next the line[0] is checked if it is a comment(\#) or an empty line (\textbackslash n). If a pointer is returned by the $strstr$ operation a 1 is returned otherwise a 0 is returned. A zero can be returned due to a comment or empty line or that the line is not an input.

\begin{lstlisting}
int isOutput(char *line)
\end{lstlisting}
This function is the same as $isInput$ except that it checks for ``output" instead of ``input".

\begin{lstlisting}
int isGate(char *line)
\end{lstlisting}
 This function is also the same as $isInput$ except that it checks if it is not a comment, not an empty line, not an input and not an output. When this is true, it should be a gate.

\begin{lstlisting}
void netlist_statistics(FILE *fp, int *no_inputs, int *no_outputs)
\end{lstlisting}
This function read trough the whole file and counts the number of inputs and outputs with the use of $isInput$ and $isOutput$. 

\begin{lstlisting}
gate_type determine_gate_type(char *str)
\end{lstlisting}
This function converts the input string to lower case. First with $isGate$ it is checked if the string contains a gate statement then compares it the string to nand, and, xnor, xor, nor,or and not with $strstr$ if there is no NULL pointer returned the gate is of the type of the name it was compared with. The correct gate type is returned.  

\begin{lstlisting}
circuit_item *get_or_insert_wire_item(node *table[], int table_size, char *str)
\end{lstlisting}
This function first creates a circuit\_item and tries to get the circuit\_item that is related to $str$ from the hash table. If a NULL pointer is returned it means that the circuit\_item is not yet in the hash table. Then the circuit\_item has to be created. Therefore first memory has to be allocated then the name of the circuit\_item is set to the input string with $strcpy$. Next the type is set to Wire and then the wire data is created. This wire data is also inserted in the circuit\_item. This circuit\_item is then returned.

\newpage

\begin{lstlisting}
void input_statement(char *line, circuit_item *inputs[], int *wr_index, node *table[], int table_size)
\end{lstlisting}
This function creates an input\_statement in the hash table. First it is checked if the input line is actually an input. Therefore a while loop through the input line is done. The reading of the line is started from line$[6]$ because ``Input \textup{(}" can be skipped. Then every char is checked if a \textbackslash n is found, it means there is no closing bracket so an error is raised. If a \textup{)} is found, if i=0 than the input name is empty and an error is raised. If i != 0 the while loop should be ended because we are at the end of the statement, a \textbackslash n is added to $name[]$ to indicate that the name is complete. Otherwise the found character is always part of the name so it is added to $name[]$ and i is incremented.

If the while loop is ended without an error, the input is added to the circuit\_item inputs at place wr\_index with the use of $get\_or\_insert\_wire\_item$ which takes table, table\_size and the extracted name as input. Next the wr\_index is incremented. 

\begin{lstlisting}
void output_statement(char *line, circuit_item *outputs[], int *wr_index, node *table[], int table_size	)
\end{lstlisting} 
This function does about the same as $input\_statement$ except it does it for output, it is added to outputs instead of inputs.

\begin{lstlisting}
void gate_statement(char *line, node *table[], int table_size)
\end{lstlisting}
This function creates a gate with its corresponding inputs and outputs. There are three things needed to make a gate:  gate\_type,output\_name and the list of inputs. Therefore the input line is processed. This is done by three while loops, for every object needed for a gate one. 

The first while loop is to detect the output\_name. First there is checked for characters that should not be in a gate name: \textup{ ( , ) }, : , `,' , \textbackslash 0 ,\textbackslash n and \#. When one of these is detected, an error is raised and the while loop is stopped. If a space is read, we just go to the next character. Because the first part of the input line is the output name, the characters are added to output\_name till a \= is detected. 

The second while loops starts where the first while loop stopped in the input line. Again there is checked for characters that should not be there. When a \textup{(} is detected it means the gate\_name is completed. Otherwise the character is just added to the gate type string and the next character is processed. 

The third while loop starts where the second while loop stopped in the input line. Here is also the check for unwanted characters. When a \textup{)} is read, it is known that the end of the statement is reached otherwise the character is just added to the input list. 

Subsequently the gate type name is converted to a gate\_type with the use of $determine\_gate\_type$. The output wire is received by using $get\_or\_insert\_wire\_item$ and the determined output\_name. Then memory for a circuit\_item is allocated. The name of the circuit\_item is set to the gate\_type + the output\_name. The type is set to Gate and the circuit\_item is inserted in the hash table. Then a s\_gate is created, the type is set to the gate\_type that was received from $determine\_gate\_type$. The number of inputs in input\_list is counted with $count\_occurences$ and set to the s\_gate. 

At least the list of inputs is split on the , by using $strtok$. Then there is looped trough all inputs and they are added as wires that are connected to the gate. 

\begin{lstlisting}
int count_occurences(char *line, char id)
\end{lstlisting}
This function counts the number of occurrences of id in line by looping over all characters.

\begin{lstlisting}
void read_netlist(FILE *fp, s_interface *interface, node *table[], int table_size)
\end{lstlisting}
This function first uses $netlist\_statistics$ to determine the number of inputs and outputs in the input file. Then it sets the number of inputs and outputs of the interface to these values. Then it allocates memory for the inputs and outputs. Subsequently the file is read line by line determining if it is an input, output or gate calling input\_statement, output\_statement or gate\_statement respectively. 

\newpage

\begin{lstlisting}
void write_netlist(FILE *fp_out, s_interface *interface, node *table[], int table_size)
\end{lstlisting}
This function writes a new file from all the data that is in the hash table. First a loop over all inputs is done to write all inputs to the file, these inputs are requested from interface. Subsequently the same is done for all outputs. 

Then all elements of the table have to be read. There is looped trough all nodes of the table. It is checked if the type of the item in the table is a gate. If so $generate\_gate\_line$ is called. When this function does not return zero, the string generated by $generate\_gate\_line$ is printed. Then the next node of the element in the table is checked. This happens as long as there are nodes in the element otherwise it goes to the next element in the table.

\begin{lstlisting}
int generate_gate_line(s_gate gate, char *line)
\end{lstlisting} 
This function assembles the gate line. First the line is started with the output wire name, then an = is added. Next the gate type is determined and converted to text. Then a textup{(} to start the input list is added. Then a loop is started that loops over all inputs of the gate and gets the name of the input which is added to the input list followed by a ,  . At last a \textup{)} is added to finish the line. The length of the line is returned. 

\begin{lstlisting}
void free_circuititem(circuit_item *item)
\end{lstlisting}
This function is used to clear circuit\_items from the memory. If the type of the circuit\_item is gate than it also has to free the inputs, and if it's a wire, it also has to free the outputs.

\begin{lstlisting}
int main(int argc, char ** argv)
\end{lstlisting}
The main is used to open the file that is specified by the argument 1 of the function. By default output.bench is used as output file however when a second argument is detected, this argument is used as output file. 

The interface and hash table are created in the main function. After that $read\_netlist$ and $write\_netlist$ are called. At the end the hash table is cleaned and the memory is deallocated. 

\section{Hash}

\begin{lstlisting}
void clean_hash(node *table[], int size)
\end{lstlisting}
This function is used to free the memory that was allocated to create the hash table, and also free the memory of all the items that where in the hash table.
\end{document}